﻿#pragma once
#include <iostream>
#include <vector>
#include <string>

struct HashFuncBKDR
{
	/// @detail 本 算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
	// ⼀书被展⽰⽽得 名，是⼀种简单快捷的hash算法，也是Java⽬前采⽤的字符串的Hash算法累乘因⼦为31。
	size_t operator()(const std::string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 31;
			hash += ch;
		}
		return hash;
	}
};
struct HashFuncAP
{
	// 由Arash Partow发明的⼀种hash算法。
	size_t operator()(const std::string& s)
	{
		size_t hash = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0) // 偶数位字符
			{
				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
			}
			else // 奇数位字符
			{
				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >>
					5)));
			}
		}
		return hash;
	}
};

struct HashFuncDJB
{
	// 由Daniel J. Bernstein教授发明的⼀种hash算法。
	size_t operator()(const std::string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}
		return hash;
	}
};

namespace bit
{
	template<size_t N = -1>
	class BitSet
	{
	public:
		BitSet()
		{
			_bitset.resize(N / 32 + 1,0);
		}

		void Set(size_t n)
		{
			int i = n / 32;
			int j = n % 32;
			_bitset[i] |= (1 << j);
		}

		void Reset(size_t n)
		{
			int i = n / 32;
			int j = n % 32;
			_bitset[i] &= ~(1 << j);
		}

		bool Test(size_t n)
		{	
			int i = n / 32;
			int j = n % 32;
			return _bitset[i] & (1 << j);
		}

		size_t Size()
		{
			return  _bitset.size();
		}

	private:
		std::vector<size_t> _bitset;
	};

	template<size_t N = -1>
	class TwoBitSet
	{
	public:
		void Set(size_t n)
		{
			if (!_bit1.Test(n) && !_bit2.Test(n))
			{
				//00 -> 01
				_bit2.Set(n);
			}
			else if (!_bit1.Test(n) && _bit2.Test(n))
			{
				//01 -> 10
				_bit1.Set(n);
				_bit2.Reset(n);
			}
			else if (_bit1.Test(n) && !_bit2.Test(n))
			{
				//10 -> 11
				_bit2.Set(n);
			}
		}

		size_t GetCount(size_t n)
		{
			if (!_bit1.Test(n) && !_bit2.Test(n))
			{
				//00 0次
				return 0;
			}
			else if (!_bit1.Test(n) && _bit2.Test(n))
			{
				//01 1次
				return 1;
			}
			else if (_bit1.Test(n) && !_bit2.Test(n))
			{
				//10 2次
				return 2;
			}
			else
			{
				return 3;
			}
		}

	private:
		BitSet<N> _bit1;
		BitSet<N> _bit2;

	};
	void test_bitset2()
	{
		bit::TwoBitSet<100> tbs;
		int a[] = {1,2,2,3,3,3,4,4};
		for (auto e : a)
		{
			tbs.Set(e);
		}
		for (size_t i = 0; i < 100; ++i)
		{
			//cout << i << "->" << tbs.GetCount(i) << endl;
			if (tbs.GetCount(i) == 1 || tbs.GetCount(i) == 2)
			{
				std::cout << i << std::endl;
			}
		}
	}

	template<size_t N,
			 size_t X = 5,
			 class K = std::string,
			 class Hashfunc1 = HashFuncBKDR,
			 class Hashfunc2 = HashFuncAP,
			 class Hashfunc3 = HashFuncDJB>
	class BloomFilter
	{
	public:
		void Set(const K& key)
		{
			size_t bit1 = Hashfunc1()(key) % M;
			size_t bit2 = Hashfunc2()(key) % M;
			size_t bit3 = Hashfunc3()(key) % M;

			_bits.Set(bit1);
			_bits.Set(bit2);
			_bits.Set(bit3);


		}

		bool Test(const K& key)
		{
			size_t bit1 = Hashfunc1()(key) % M;
			if (!_bits.Test(bit1))	
				return false;
			size_t bit2 = Hashfunc2()(key) % M;
			if (!_bits.Test(bit2))	
				return false;
			size_t bit3 = Hashfunc3()(key) % M;
			if (!_bits.Test(bit3))	
				return false;
			return true;
		}

	private:
		static const size_t M = N * X;
		BitSet<M> _bits;
	};

	void TestBloomFilter1()
	{
		std::string strs[] = { "百度","字节","腾讯" };
		BloomFilter<10> bf;
		for (auto& s : strs)
		{
			bf.Set(s);
		}
		for (auto& s : strs)
		{
			std::cout << bf.Test(s) << std::endl;
		}
		for (auto& s : strs)
		{
			std::cout << bf.Test(s + 'a') << std::endl;
		}
		std::cout << bf.Test("摆渡") << std::endl;
		std::cout << bf.Test("百度") << std::endl;
	}
}